#define DEBUG
#include <cstdio>

using namespace std;

const int maxm=100000;

int max(int a, int b) {
	return a>b ? a : b;
}

class Splay {
	public:
		int n=0, root, r, fa[maxm+1], k[maxm+1], son[maxm+1][2], v[maxm+1], mark[maxm+1], f[maxm+1], s[maxm+1][2];

		int side(int o) {
			return son[fa[o]][1]==o;
		}

		void pushDown(int o) {
			if (mark[o]) {
				v[o] += mark[o];
				if (son[o][0]) mark[son[o][0]] += mark[o];
				if (son[o][1]) mark[son[o][1]] += mark[o];
				mark[o] = 0;
			}
		}

		void update(int o) {
			if (fa[o]) update(fa[o]);
			pushDown(o);
		}

		void rotate(int x) {
			int y=fa[x], t=side(x);
			if (fa[y]) son[fa[y]][side(y)] = x;
			fa[x] = fa[y];
			if (son[x][!t]) fa[son[x][!t]]=y;
			son[y][t] = son[x][!t];
			son[x][!t] = y, fa[y]=x;
		}

		int splay(int o, int tar=0) {
			tar = tar==o ? 0 : tar;
			update(o);
			for (; fa[o]!=tar; ) {
				if (fa[fa[o]]!=tar && side(fa[o])==side(o)) rotate(fa[o]);
				rotate(o);
			}
			if (!tar) root=o;
			return o;
		}

		int addNode(int f, int key, int sid) {
			son[f][sid] = ++n;
			fa[n] = f;
			k[n] = key;
			return n;
		}

		int push(int key, int o=0) {
			if (root) {
				o = o ? o : root;
				pushDown(o);
				if (key<k[o]) return son[o][0] ? push(key, son[o][0]) : addNode(o, key, 0);
				else return son[o][1] ? push(key, son[o][1]) : addNode(o, key, 1);
			} else {
				k[++n] = key;
				return root=n;
			}
		}

		int getMin(int o=0) {
			o = o ? o : root;
			pushDown(o);
			return son[o][0] ? getMin(son[o][0]) : o;
		}

		int getMax(int o=0) {
			o = o ? o : root;
			pushDown(o);
			return son[o][1] ? getMax(son[o][1]) : o;
		}

		int prev(int o) {
			splay(o);
			return son[o][0] ? getMax(son[o][0]) : 0;
		}

		int next(int o) {
			splay(o);
			return son[o][1] ? getMin(son[o][1]) : 0;
		}

		int delMinOrMax(int o) {
			splay(o);
			int t=son[o][0]==0;
			fa[son[o][t]] = 0;
			root = son[o][t];
			k[o] = son[o][t] = 0;
			return root;
		}

		void add(int u, int v, int val) {
			u = prev(u), v = next(v);
			if (!u && !v) {
				mark[root] += val;
			} else if (!u) {
				splay(v);
				mark[son[v][0]] += val;
			} else if (!v) {
				splay(u);
				mark[son[u][1]] += val;
			} else {
				splay(u), splay(v, u);
				if (son[v][0]) mark[son[v][0]] += val;
			}
		}

		void addFromMinOrMax(int o, int val) {
			splay(o);
			int t=son[o][0]==0;
			mark[son[o][t]] += val;
		}
};

void update(Splay &s, int p, int c) {
	int u=s.f[p], v=c==2 ? s.getMax() : s.getMin(), t=c==2;
	if (c==2) s.add(u, v, 1);
	else s.add(v, u, 1);
	int x=s.s[p][t], y=s.f[p];
	s.v[p] = 1;
	s.s[y][!t] = x, s.f[x] = y;
	s.s[p][t] = s.r, s.f[s.r] = p;
	s.r = p;
}

int main() {
	freopen("splay.in", "r", stdin);
	freopen("splay.out", "w", stdout);

	static Splay s;
	int m;
	scanf("%d", &m);
	for (int i=1; i<=m; i++) {
		int c, key;
		scanf("%d", &c);
		if (c==1) {
			scanf("%d", &key);
			int p=s.push(key), l=s.prev(p), r=s.next(p);
			if (s.v[l]>s.v[r]) {
				s.v[p] = s.v[l]+1;
				s.s[l][1] = p;
				s.f[p] = l;
			} else {
				s.v[p] = s.v[r]+1;
				s.s[r][0] = p;
				s.f[p] = r;
			}
			if (s.f[p]==0) s.r = p;
			printf("%d\n", s.v[p]);
		} else if (c==2 || c==3) {
			int p=c==2 ? s.getMin() : s.getMax(), ans=s.v[p];
			printf("%d\n", ans);
			if (ans>1) update(s, p, c);
		} else if (c==4 || c==5) {
			int p=c==4 ? s.getMin() : s.getMax(), ans=s.v[p];
			printf("%d\n", ans);
			if (ans>1) update(s, p, c-2);
			s.addFromMinOrMax(p, -1);
			int t=s.s[p][c==4 ? 1 : 0];
			s.f[t] = 0, s.s[p][c==4 ? 1 : 0]=0;
			s.r = t;
			s.delMinOrMax(p);
		}
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}
